// 添加与搜索单词 - 数据结构设计

package Leetcode;

class WordDictionary {
    WordDictionary[] children;
    boolean isLeaf;

    public WordDictionary() {
        children = new WordDictionary[26];
        isLeaf = false;
    }

    public void addWord(String word) {
        WordDictionary wd = this;
        // 遍历每个字符
        for (char c : word.toCharArray()) {
            // 如果对应节点为null，则创建
            if (wd.children[c - 'a'] == null)
                wd.children[c - 'a'] = new WordDictionary();
            wd = wd.children[c - 'a'];
        }
        // 最后一个节点是叶子节点
        wd.isLeaf = true;
    }

    public boolean search(String word) {
        return Reverse(word, 0, this);
    }

    public boolean Reverse(String word, int current, WordDictionary wd) {
        if (current == word.length())
            return wd.isLeaf;   // 这里一定要返回是否是叶子，如果直接返回true，会出现word是子串的情况
        boolean result = false;
        char c = word.charAt(current);
        if (c != '.' && wd.children[c - 'a'] == null)
            return false;
        else if (c != '.' && wd.children[c - 'a'] != null) {
            result = result | Reverse(word, current + 1, wd.children[c - 'a']);
        } else { // c=='.'
            for (int i = 0; i < 26; i++) {
                if (wd.children[i] != null)
                    result = result | Reverse(word, current + 1, wd.children[i]);
            }
        }
        return result;
    }
}